package com.leetcode;

/**
 * Created by Z-hong on 2023/3/1.
 */

public class LeetCode10 {
    public static boolean isMatch(String s, String p) {
                if (s == null || p == null) return false;
                int m = s.length(), n = p.length();

                boolean[][] dp = new boolean[m + 1][n + 1];
                dp[0][0] = true;

                //"" 和p的匹配关系初始化，a*a*a*a*a*这种能够匹配空串，其他的是都是false。
                //  奇数位不管什么字符都是false，偶数位为* 时则: dp[0][i] = dp[0][i - 2]
                //防止哪些x*前面没字母的 例如 a* 等
                for (int i = 2; i <= n; i+= 2) {
                    if (p.charAt(i - 1) == '*') {
                        dp[0][i] = dp[0][i - 2];
                    }
                }

                for (int i = 1; i <= m; i++) {
                    for (int j = 1; j <= n; j++) {
                        char sc = s.charAt(i - 1);
                        char pc = p.charAt(j - 1);
                        //如果匹配就看前面的匹不匹配
                        if (sc == pc || pc == '.') {
                            dp[i][j] = dp[i - 1][j - 1];
                        } else if (pc == '*') {
                            //这个是*为0个
                            if (dp[i][j - 2]) {
                                dp[i][j] = true;
                            } else if (sc == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
                                //匹配成功 s往前一格查看匹配情况
                                dp[i][j] = dp[i - 1][j];
                            }
                        }
                    }
                }

                return dp[m][n];
            }



    public static void main(String[] args) {
        System.out.println(isMatch("aaa", "aa*a"));
    }

}
